{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest ZigZag Path in a Binary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #dynamic-programming #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #动态规划 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestZigZag"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉树中的最长交错路径"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一棵以&nbsp;<code>root</code>&nbsp;为根的二叉树，二叉树中的交错路径定义如下：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>选择二叉树中 <strong>任意</strong>&nbsp;节点和一个方向（左或者右）。</li>\n",
    "\t<li>如果前进方向为右，那么移动到当前节点的的右子节点，否则移动到它的左子节点。</li>\n",
    "\t<li>改变前进方向：左变右或者右变左。</li>\n",
    "\t<li>重复第二步和第三步，直到你在树中无法继续移动。</li>\n",
    "</ul>\n",
    "\n",
    "<p>交错路径的长度定义为：<strong>访问过的节点数目 - 1</strong>（单个节点的路径长度为 0 ）。</p>\n",
    "\n",
    "<p>请你返回给定树中最长 <strong>交错路径</strong>&nbsp;的长度。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/03/07/sample_1_1702.png\" style=\"height: 283px; width: 151px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>蓝色节点为树中最长交错路径（右 -&gt; 左 -&gt; 右）。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/03/07/sample_2_1702.png\" style=\"height: 253px; width: 120px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>root = [1,1,1,null,1,null,null,1,1,null,1]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>蓝色节点为树中最长交错路径（左 -&gt; 右 -&gt; 左 -&gt; 右）。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>root = [1]\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>每棵树最多有&nbsp;<code>50000</code>&nbsp;个节点。</li>\n",
    "\t<li>每个节点的值在&nbsp;<code>[1, 100]</code> 之间。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-zigzag-path-in-a-binary-tree](https://leetcode.cn/problems/longest-zigzag-path-in-a-binary-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-zigzag-path-in-a-binary-tree](https://leetcode.cn/problems/longest-zigzag-path-in-a-binary-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,null,1,1,1,null,null,1,1,null,1,null,null,null,1]', '[1,1,1,null,1,null,null,1,1,null,1]', '[1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    def longestZigZag(self, root: Optional[TreeNode]) -> int:\n",
    "        self.ans = 0\n",
    "        self.solve(root)\n",
    "        return self.ans - 1\n",
    "    \n",
    "    def solve(self,x):\n",
    "        if x is None:\n",
    "            ret = (0,0)\n",
    "        else:\n",
    "            ret = (self.solve(x.left)[1] + 1, self.solve(x.right)[0] + 1)\n",
    "        \n",
    "        self.ans = max(self.ans, max(*ret))\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def longestZigZag(self, root: TreeNode) -> int:\n",
    "        f, g = collections.defaultdict(int), collections.defaultdict(int)\n",
    "        q = collections.deque([(root, None)])\n",
    "        while len(q)>0:\n",
    "            node, parent = q.popleft()\n",
    "            if parent:\n",
    "                if parent.left == node:\n",
    "                    f[node]=g[parent] + 1\n",
    "                if parent.right == node:\n",
    "                    g[node] = f[parent] + 1\n",
    "            if node.left:\n",
    "                q.append((node.left, node))\n",
    "            if node.right:\n",
    "                q.append((node.right, node))\n",
    "\n",
    "        maxans=0\n",
    "        for _,val in f.items():\n",
    "            maxans = max(maxans, val)\n",
    "        for _,val in g.items():\n",
    "            maxans = max(maxans, val)\n",
    "        return maxans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def longestZigZag(self, root: TreeNode) -> int:\n",
    "        f = defaultdict(int)\n",
    "        g = defaultdict(int) \n",
    "        queue = deque([(root,None)])\n",
    "        while len(queue) > 0:\n",
    "            node,parent = queue.popleft()\n",
    "            if parent:\n",
    "\n",
    "                if parent.left == node:\n",
    "                    f[node] = g[parent] + 1\n",
    "                else:\n",
    "                    g[node] = f[parent] + 1\n",
    "\n",
    "            if node.left:\n",
    "                queue.append((node.left,node))\n",
    "            if node.right:\n",
    "                queue.append((node.right,node))\n",
    "\n",
    "        ans = 0\n",
    "        for _,val in f.items():\n",
    "            ans = max(ans,val)\n",
    "        for _,val in g.items():\n",
    "            ans = max(ans,val)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestZigZag(self, root: TreeNode) -> int:\n",
    "        #c1\n",
    "        f, g = collections.defaultdict(int), collections.defaultdict(int)\n",
    "        q = collections.deque([(root, None)])\n",
    "        while len(q) > 0:\n",
    "            node, parent = q.popleft()\n",
    "            if parent:\n",
    "                if parent.left == node:\n",
    "                    f[node] = g[parent] + 1\n",
    "                else:\n",
    "                    g[node] = f[parent] + 1\n",
    "            if node.left:\n",
    "                q.append((node.left, node))\n",
    "            if node.right:\n",
    "                q.append((node.right, node))\n",
    "        \n",
    "        maxans = 0\n",
    "        for _, val in f.items():\n",
    "            maxans = max(maxans, val)\n",
    "        for _, val in g.items():\n",
    "            maxans = max(maxans, val)\n",
    "        return maxans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestZigZag(self, root: Optional[TreeNode]) -> int:\n",
    "    \n",
    "        pathLength = [0]\n",
    "        leftStack = []\n",
    "        rightStack = []\n",
    "        if root.left:\n",
    "            leftStack.append(root)\n",
    "        if root.right:\n",
    "            rightStack.append(root)\n",
    "\n",
    "        while leftStack or rightStack :\n",
    "            cur_path = 0\n",
    "            if leftStack: \n",
    "                cur = leftStack.pop()\n",
    "                goLeft = True\n",
    "            else: \n",
    "                cur = rightStack.pop()\n",
    "                goLeft = False\n",
    "\n",
    "            while (cur.left and goLeft) or (cur.right and not goLeft) :\n",
    "                if goLeft:\n",
    "                    cur = cur.left\n",
    "                    if cur.left:\n",
    "                        leftStack.append(cur)                       \n",
    "                    cur_path += 1\n",
    "                    goLeft = False\n",
    "                else:\n",
    "                    cur = cur.right\n",
    "                    if cur.right:\n",
    "                        rightStack.append(cur)   \n",
    "                    cur_path += 1\n",
    "                    goLeft = True\n",
    "                   \n",
    "            pathLength.append(cur_path)\n",
    "        return max( pathLength)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestZigZag(self, root: Optional[TreeNode]) -> int:\n",
    "        f, g = defaultdict(int), defaultdict(int)\n",
    "        q = deque([(root, None)])\n",
    "        while len(q) > 0:\n",
    "            node, parent = q.popleft()\n",
    "            if parent:\n",
    "                if parent.left == node:\n",
    "                    f[node] = g[parent] + 1\n",
    "                else:\n",
    "                    g[node] = f[parent] + 1\n",
    "            if node.left:\n",
    "                q.append((node.left, node))\n",
    "            if node.right:\n",
    "                q.append((node.right, node))\n",
    "        ans = 0\n",
    "        for val in f.values():\n",
    "            ans = max(ans, val)\n",
    "        for val in g.values():\n",
    "            ans = max(ans, val)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestZigZag(self, root: Optional[TreeNode]) -> int:\n",
    "        f, g = collections.defaultdict(int), collections.defaultdict(int)\n",
    "        q = collections.deque([(root, None)])\n",
    "        while len(q) > 0:\n",
    "            node, parent = q.popleft()\n",
    "            if parent:\n",
    "                if parent.left == node:\n",
    "                    f[node] = g[parent] + 1\n",
    "                else:\n",
    "                    g[node] = f[parent] + 1\n",
    "            if node.left:\n",
    "                q.append((node.left, node))\n",
    "            if node.right:\n",
    "                q.append((node.right, node))\n",
    "        res = 0\n",
    "        for _, val in f.items():\n",
    "            res = max(res, val)\n",
    "        for _, val in g.items():\n",
    "            res = max(res, val)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestZigZag(self, root: TreeNode) -> int:\n",
    "        f, g = collections.defaultdict(int), collections.defaultdict(int)\n",
    "        q = collections.deque([(root, None)])\n",
    "        while len(q) > 0:\n",
    "            node, parent = q.popleft()\n",
    "            if parent:\n",
    "                if parent.left == node:\n",
    "                    f[node] = g[parent] + 1\n",
    "                else:\n",
    "                    g[node] = f[parent] + 1\n",
    "            if node.left:\n",
    "                q.append((node.left, node))\n",
    "            if node.right:\n",
    "                q.append((node.right, node))\n",
    "        \n",
    "        maxans = 0\n",
    "        for _, val in f.items():\n",
    "            maxans = max(maxans, val)\n",
    "        for _, val in g.items():\n",
    "            maxans = max(maxans, val)\n",
    "        return maxans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestZigZag(self, root: Optional[TreeNode]) -> int:\n",
    "        # 下一个希望是 left - right + else 0\n",
    "\n",
    "        ans = 0\n",
    "        root.val = 0\n",
    "        queue = deque([root])\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            currVal = node.val\n",
    "            if node.left:\n",
    "                if currVal >= 0:\n",
    "                    node.left.val = 1\n",
    "                else:\n",
    "                    node.left.val = -currVal + 1\n",
    "                ans = max(ans, abs(node.left.val))\n",
    "                queue.append(node.left)\n",
    "            if node.right:\n",
    "                if currVal <= 0:\n",
    "                    node.right.val = -1\n",
    "                else:\n",
    "                    node.right.val = -currVal - 1\n",
    "                ans = max(ans, abs(node.right.val))\n",
    "                queue.append(node.right)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestZigZag(self, root: TreeNode) -> int:\n",
    "        f, g = collections.defaultdict(int), collections.defaultdict(int)\n",
    "        q = collections.deque([(root, None)])\n",
    "        res = 0\n",
    "        while len(q) > 0:\n",
    "            node, parent = q.popleft()\n",
    "            if parent:\n",
    "                if parent.left == node:\n",
    "                    f[node] = g[parent] + 1\n",
    "                else:\n",
    "                    g[node] = f[parent] + 1\n",
    "            if node.left:\n",
    "                q.append((node.left, node))\n",
    "            if node.right:\n",
    "                q.append((node.right, node))\n",
    "            res = max(f[node], g[node], res)\n",
    "        \n",
    "        # maxans = 0\n",
    "        # for _, val in f.items():\n",
    "        #     maxans = max(maxans, val)\n",
    "        # for _, val in g.items():\n",
    "        #     maxans = max(maxans, val)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "RIGHT = 1\n",
    "LEFT = 0\n",
    "class Solution:\n",
    "    def longestZigZag(self, root: Optional[TreeNode]) -> int:\n",
    "        root.l_num = 0\n",
    "        root.r_num = 0\n",
    "        max_len = 0\n",
    "        stack = [root]\n",
    "        \n",
    "        while stack:\n",
    "            cur = stack.pop(-1)\n",
    "            max_len = max([max_len, cur.l_num, cur.r_num])\n",
    "            if cur.right:\n",
    "                cur.right.r_num = cur.l_num + 1\n",
    "                cur.right.l_num = 0\n",
    "                stack.append(cur.right)\n",
    "            if cur.left:\n",
    "                cur.left.l_num = cur.r_num + 1\n",
    "                cur.left.r_num = 0\n",
    "                stack.append(cur.left)\n",
    "\n",
    "        return max_len\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestZigZag(self, root: TreeNode) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        \n",
    "        root.visited = False\n",
    "        trvs_list = list()\n",
    "        trvs_list.append(root)\n",
    "\n",
    "        curr_node = None\n",
    "        to_left = 0\n",
    "        to_right = 0\n",
    "        max_path = 0\n",
    "        while len(trvs_list) > 0:\n",
    "            curr_node = trvs_list.pop()\n",
    "            if curr_node.visited:\n",
    "                to_left = 0\n",
    "                to_right = 0\n",
    "                if curr_node.left is not None:\n",
    "                    to_left = curr_node.left.to_right + 1\n",
    "                    if to_left > max_path:\n",
    "                        max_path = to_left\n",
    "                if curr_node.right is not None:\n",
    "                    to_right = curr_node.right.to_left + 1\n",
    "                    if to_right > max_path:\n",
    "                        max_path = to_right\n",
    "                curr_node.to_left = to_left\n",
    "                curr_node.to_right = to_right\n",
    "                continue\n",
    "            \n",
    "            curr_node.visited = True\n",
    "            trvs_list.append(curr_node)\n",
    "            if curr_node.left is not None:\n",
    "                curr_node.left.visited = False\n",
    "                trvs_list.append(curr_node.left)\n",
    "            if curr_node.right is not None:\n",
    "                curr_node.right.visited = False\n",
    "                trvs_list.append(curr_node.right)\n",
    "        \n",
    "        return max_path\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestZigZag(self, root: TreeNode) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        \n",
    "        root.visited = False\n",
    "        trvs_list = list()\n",
    "        trvs_list.append(root)\n",
    "\n",
    "        curr_node = None\n",
    "        to_left = 0\n",
    "        to_right = 0\n",
    "        max_path = 0\n",
    "        while len(trvs_list) > 0:\n",
    "            curr_node = trvs_list.pop()\n",
    "            if curr_node.visited:\n",
    "                to_left = 0\n",
    "                to_right = 0\n",
    "                if curr_node.left is not None:\n",
    "                    to_left = curr_node.left.to_right + 1\n",
    "                    if to_left > max_path:\n",
    "                        max_path = to_left\n",
    "                if curr_node.right is not None:\n",
    "                    to_right = curr_node.right.to_left + 1\n",
    "                    if to_right > max_path:\n",
    "                        max_path = to_right\n",
    "                curr_node.to_left = to_left\n",
    "                curr_node.to_right = to_right\n",
    "                continue\n",
    "            \n",
    "            curr_node.visited = True\n",
    "            trvs_list.append(curr_node)\n",
    "            if curr_node.left is not None:\n",
    "                curr_node.left.visited = False\n",
    "                trvs_list.append(curr_node.left)\n",
    "            if curr_node.right is not None:\n",
    "                curr_node.right.visited = False\n",
    "                trvs_list.append(curr_node.right)\n",
    "        \n",
    "        return max_path\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, root: TreeNode):\n",
    "        if root.left:\n",
    "            self.dfs(root.left)\n",
    "            root.lz = root.left.rz + 1\n",
    "        else:\n",
    "            root.lz = 0\n",
    "        if root.right:\n",
    "            self.dfs(root.right)\n",
    "            root.rz = root.right.lz + 1\n",
    "        else:\n",
    "            root.rz = 0\n",
    "        self.ans = max(self.ans, root.lz, root.rz)\n",
    "        \n",
    "    def longestZigZag(self, root: TreeNode) -> int:\n",
    "        if root == None: return 0\n",
    "        self.ans = 0\n",
    "        self.dfs(root)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def longestZigZag(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return -1\n",
    "        self.max = 0\n",
    "        self._longest(root)\n",
    "        return self.max\n",
    "    \n",
    "    def _longest(self, r):\n",
    "        if not r:\n",
    "            return [-1, -1]\n",
    "        ans = [self._longest(r.left)[1]+1, self._longest(r.right)[0]+1]\n",
    "        m = max(ans)\n",
    "        if m > self.max:\n",
    "            self.max = m\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution(object):\n",
    "    def longestZigZag(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        self.res = 0\n",
    "        self.get_longest(root)\n",
    "        return self.res - 1\n",
    "\n",
    "    def get_longest(self,curnode):\n",
    "        if not curnode:\n",
    "            return (0,0)\n",
    "        left_left,left_right = self.get_longest(curnode.left)\n",
    "        right_left,right_right =self.get_longest(curnode.right)\n",
    "\n",
    "        cur_left = left_right+1\n",
    "        cur_right = right_left+1\n",
    "        if self.res<max(cur_left,cur_right):\n",
    "            self.res = max(cur_left,cur_right)\n",
    "        return (cur_left,cur_right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def longestZigZag(self, root: TreeNode) -> int:\n",
    "        self.maxCnt = 0\n",
    "        if not root or (not root.left and not root.right):\n",
    "            return 0\n",
    "        self.helper(root, True)\n",
    "        return self.maxCnt\n",
    "    \n",
    "    def helper(self, root, isLeft):\n",
    "        if not root:\n",
    "            return 0\n",
    "        rightCnt = self.helper(root.right, False)\n",
    "        leftCnt = self.helper(root.left, True)\n",
    "        if leftCnt > self.maxCnt or rightCnt > self.maxCnt:\n",
    "            self.maxCnt = max(leftCnt, rightCnt)\n",
    "        if isLeft:\n",
    "            return rightCnt + 1\n",
    "        else:\n",
    "            return leftCnt + 1\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def longestZigZag(self, root: TreeNode) -> int:\n",
    "        self.res = 0\n",
    "        self.longest(root)\n",
    "        return self.res\n",
    "    def longest(self,root):\n",
    "        left = 0 \n",
    "        right = 0\n",
    "        if root.left is not None:\n",
    "            left = 1 + self.longest(root.left)[1]\n",
    "        else:\n",
    "            left = 0\n",
    "        if root.right is not None:\n",
    "            right = 1 + self.longest(root.right)[0]\n",
    "        else:\n",
    "            right = 0\n",
    "        if left > self.res:\n",
    "            self.res = left\n",
    "        if right > self.res:\n",
    "            self.res = right\n",
    "        return left,right\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def longestZigZag(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        \n",
    "        self.ret = 0\n",
    "        \n",
    "        self.helper(root.left, True)\n",
    "        self.helper(root.right, False)\n",
    "        return self.ret\n",
    "\n",
    "    def helper(self, node: TreeNode, last_left):\n",
    "        if not node:\n",
    "            return 0\n",
    "        \n",
    "        # self.res is changed while calling left and right\n",
    "        left = self.helper(node.left, True)\n",
    "        right = self.helper(node.right, False)\n",
    "        \n",
    "        if last_left:\n",
    "            ret = right + 1  \n",
    "        else:\n",
    "            ret = left + 1\n",
    "            \n",
    "        self.ret = max(self.ret, ret)\n",
    "        \n",
    "        return ret\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestZigZag(self, root: TreeNode) -> int:\n",
    "        self.ans = 0\n",
    "        self.dfs(root)\n",
    "        return self.ans\n",
    "        \n",
    "    def dfs(self, node):\n",
    "        node.f_left = node.f_right = 0\n",
    "        if node.left is not None:\n",
    "            self.dfs(node.left)\n",
    "            node.f_left = node.left.f_right + 1\n",
    "        if node.right is not None:\n",
    "            self.dfs(node.right)\n",
    "            node.f_right = node.right.f_left + 1\n",
    "        self.ans = max(self.ans, node.f_left, node.f_right)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = 0\n",
    "\n",
    "    def longestZigZag(self, root: TreeNode) -> int:\n",
    "        self.dfs(root,0,0) # 0: 左边子树\n",
    "        self.dfs(root,1,0) # 1: 右子树\n",
    "        return self.res\n",
    "\n",
    "    def dfs(self,node,direction,length):\n",
    "        if not node:\n",
    "            return \n",
    "        self.res = max(self.res,length)\n",
    "        if direction == 0:\n",
    "            self.dfs(node.left,0,1)\n",
    "            self.dfs(node.right,1,length+1)\n",
    "        else:\n",
    "            self.dfs(node.left,0,length+1)\n",
    "            self.dfs(node.right,1,1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestZigZag(self, root: TreeNode) -> int:\n",
    "        self.res = 0\n",
    "        self.maxPath(root)\n",
    "        return self.res\n",
    "\n",
    "    def maxPath(self, root):\n",
    "        if not root:\n",
    "            return 0, 0\n",
    "        if root and not root.left and not root.right:\n",
    "            return 1, 1\n",
    "        leftLeft, leftRight = self.maxPath(root.left)\n",
    "        rightLeft, rightRight = self.maxPath(root.right)\n",
    "\n",
    "        self.res = max(self.res, max(leftRight + 1, rightLeft + 1) - 1)\n",
    "        return leftRight + 1, rightLeft + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.maxZigZag = 0\n",
    "\n",
    "    def _longestZigZag(self, root, accumulate, perIsLeft):\n",
    "        self.maxZigZag = max(self.maxZigZag, accumulate)\n",
    "        if root == None or (root.left == None and root.right == None):\n",
    "            return\n",
    "\n",
    "        if root.left != None:\n",
    "            nextAccumulate = 1 if perIsLeft == True else accumulate + 1\n",
    "            self._longestZigZag(root.left, nextAccumulate, True)\n",
    "\n",
    "        if root.right != None:\n",
    "            nextAccumulate = 1 if perIsLeft == False else accumulate + 1\n",
    "            self._longestZigZag(root.right, nextAccumulate, False)\n",
    "\n",
    "\n",
    "    def longestZigZag(self, root: TreeNode) -> int:\n",
    "        self._longestZigZag(root, 0, None)\n",
    "        return self.maxZigZag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    def longestZigZag(self, root: TreeNode) -> int:\n",
    "        \"\"\"\n",
    "        DP思想，先定义节点状态，再遍历每个节点，由父节点状态推出子节点\n",
    "\n",
    "        定义状态：每个节点的状态代表遍历到该节点为止的longestZigZag\n",
    "        如何由父节点推出子节点？分析可知，下一个节点的状态由几个因素决定：\n",
    "        1. 父节点是左孩子还是右孩子\n",
    "        2. 父节点的longestZigZag\n",
    "\n",
    "        遍历可以用DFS或BFS\n",
    "        1. 节点状态可以用tuple表达，跟节点一起push到栈或者队列中\n",
    "        2. 如果DFS递归，节点状态可以用参数扩展法表达\n",
    "        \"\"\"\n",
    "        \n",
    "        self.ans = 0\n",
    "        self.dfs(root, True, 0)\n",
    "        self.dfs(root, False, 0)\n",
    "        return self.ans\n",
    "\n",
    "\n",
    "    def dfs(self, root: TreeNode, leftChild: bool, distance: int) -> None:\n",
    "        if not root: return\n",
    "        \n",
    "        # process the cur node\n",
    "        self.ans = max(self.ans, distance)\n",
    "        \n",
    "        # visit left and right node\n",
    "        if leftChild:\n",
    "            self.dfs(root.right, False, distance + 1)\n",
    "            self.dfs(root.left, True, 1)\n",
    "        else:\n",
    "            self.dfs(root.left, True, distance + 1)\n",
    "            self.dfs(root.right, False, 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestZigZag(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        res = self.pureRecursion(root)\n",
    "        return res[2] - 1\n",
    "    def pureRecursion(self, root):\n",
    "        if not root:\n",
    "            return 0, 0, 0\n",
    "        leftLeft, leftRight, leftMax = self.pureRecursion(root.left)\n",
    "        rightLeft, rightRight, rightMax = self.pureRecursion(root.right)\n",
    "        curLeftMax, curRightMax = leftRight + 1, rightLeft + 1\n",
    "        maxlen = max(curLeftMax, curRightMax, leftMax, rightMax)\n",
    "        return curLeftMax, curRightMax, maxlen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestZigZag(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        ret = 0\n",
    "\n",
    "        def dfs(node):\n",
    "            nonlocal ret\n",
    "            left = right = 0\n",
    "            if node.left:\n",
    "                left = dfs(node.left)[1] + 1\n",
    "                if left > ret: ret = left\n",
    "            if node.right:\n",
    "                right = dfs(node.right)[0] + 1\n",
    "                if right > ret: ret = right\n",
    "\n",
    "            return left, right\n",
    "        \n",
    "        dfs(root)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestZigZag(self, root: TreeNode) -> int:\n",
    "        res = 0\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 0, 0\n",
    "            # 左子树的最大交错路径，必定是左子树的右子树，所以左子树的左子树用不到\n",
    "            _, lr = dfs(root.left)\n",
    "            # 右子树的最大交错路径，必定是右子树的左子树，所以右子树的右子树用不到\n",
    "            rl, _ = dfs(root.right)\n",
    "            nonlocal res\n",
    "            l = r = 0\n",
    "            if root.left:\n",
    "                l = 1 + lr  # 如果左子树存在的话，左子树的右子树+1\n",
    "            if root.right:\n",
    "                r = 1 + rl\n",
    "            res = max(res, l, r)\n",
    "            return l, r\n",
    "        dfs(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestZigZag(self, root: Optional[TreeNode]) -> int:\n",
    "        maxans=0\n",
    "        def dfs(root,flag):\n",
    "            nonlocal maxans\n",
    "            if root==None:\n",
    "                return -1\n",
    "            if flag==1:\n",
    "                val1=dfs(root.right, 1)\n",
    "                val2=dfs(root.right,0)+1\n",
    "                maxans=max(maxans,val1,val2)\n",
    "                return val2\n",
    "            elif flag==0:\n",
    "                val1=dfs(root.left,0)\n",
    "                val2=dfs(root.left,1)+1\n",
    "                maxans=max(maxans,val1,val2)\n",
    "                return val2\n",
    "        dfs(root,1)\n",
    "        dfs(root,0)\n",
    "        return maxans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestZigZag(self, root: Optional[TreeNode]) -> int:\n",
    "        longest_dist = 0\n",
    "        def _dfs(node):\n",
    "            nonlocal longest_dist\n",
    "            left = 0\n",
    "            right = 0\n",
    "            if not node:\n",
    "                return left, right\n",
    "            if node.left:\n",
    "                left = _dfs(node.left)[1] + 1\n",
    "            if node.right:\n",
    "                right = _dfs(node.right)[0] + 1\n",
    "            longest_dist = max(left, right, longest_dist)\n",
    "            return left, right\n",
    "        _dfs(root)\n",
    "        return longest_dist\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestZigZag(self, root: Optional[TreeNode]) -> int:\n",
    "        # 递归计算每个节点往左和往右的最长交错路径\n",
    "        if root is None: return -1\n",
    "\n",
    "        def search(root, direction, max_val):\n",
    "            if root is None: return -1, max_val\n",
    "            if direction == \"L\":\n",
    "                cur_val, max_val = search(root.left, \"R\", max_val)\n",
    "                _, max_val = search(root.left, \"L\", max_val)\n",
    "\n",
    "            else:\n",
    "                cur_val, max_val = search(root.right, \"L\", max_val)\n",
    "                _, max_val = search(root.right, \"R\", max_val)\n",
    "            cur_val += 1\n",
    "            max_val = max(cur_val, max_val)\n",
    "            return cur_val, max_val\n",
    "        _, max_val = search(root, \"L\", 0)\n",
    "        _, max_val = search(root, \"R\", max_val)\n",
    "        return max_val\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestZigZag(self, root: Optional[TreeNode]) -> int:\n",
    "        res = 0\n",
    "\n",
    "        def dfs(root, isLeftChild, max_len):\n",
    "            nonlocal res\n",
    "            res = max(res, max_len)\n",
    "            if root.left is not None:\n",
    "                dfs(root.left, True, 1 if isLeftChild else max_len + 1)\n",
    "            if root.right is not None:\n",
    "                dfs(root.right, False, max_len + 1 if isLeftChild else 1)\n",
    "\n",
    "        dfs(root, True, 0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestZigZag(self, root: Optional[TreeNode]) -> int:\n",
    "        path=[]\n",
    "        r=[]\n",
    "        def dfs(node,index):\n",
    "            \n",
    "            if node==None:\n",
    "                return -1\n",
    "            if index==0:\n",
    "                a=dfs(node.left,index=0)\n",
    "                b=dfs(node.right,index=1)\n",
    "                r.append(max(a+1,b+1))\n",
    "                return b+1\n",
    "            if index==1:\n",
    "                a=dfs(node.left,index=0)\n",
    "                b=dfs(node.right,index=1)\n",
    "                r.append(max(a+1,b+1))\n",
    "                return a+1\n",
    "        \n",
    "        dfs(root,0)\n",
    "        #print(r)\n",
    "        return max(r)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestZigZag(self, root: Optional[TreeNode]) -> int:\n",
    "        def process(node):\n",
    "            if node and not node.left and not node.right:\n",
    "                return 0, 0, 0\n",
    "\n",
    "            if not node:\n",
    "                return -1, -1, -1\n",
    "\n",
    "            ll_max, lr_max, lno_max = process(node.left)\n",
    "            rl_max, rr_max, rno_max = process(node.right)\n",
    "\n",
    "            # 包括当前节点的最大值，不包括当前节点的最大值\n",
    "\n",
    "            return 1 + lr_max, 1 + rl_max, max(lno_max, rno_max, 1 + lr_max, 1 + rl_max)\n",
    "\n",
    "        return max(process(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self, node: Optional[TreeNode], leftmax: dict, rightmax: dict) -> int:\n",
    "        if node is None:\n",
    "            return 0\n",
    "        if node.left:\n",
    "            self.dfs(node.left, leftmax, rightmax)\n",
    "        if node.right:\n",
    "            self.dfs(node.right, leftmax, rightmax)\n",
    "        leftmax[node] = rightmax[node.left] + 1 if node.left else 0\n",
    "        rightmax[node] = leftmax[node.right] + 1 if node.right else 0\n",
    "        return \n",
    "\n",
    "    def longestZigZag(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        if root:\n",
    "            leftmax = {}\n",
    "            rightmax = {}\n",
    "            self.dfs(root, leftmax, rightmax)\n",
    "            for k in leftmax.keys():\n",
    "                if leftmax[k] > ans:\n",
    "                    ans = leftmax[k]\n",
    "            for k in rightmax.keys():\n",
    "                if rightmax[k] > ans:\n",
    "                    ans = rightmax[k]\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    def longestZigZag(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(root):\n",
    "            if not isinstance(root, TreeNode):\n",
    "                return [0, 0, 0]\n",
    "            ret = [0, 0, 0]\n",
    "            if root.left:\n",
    "                lm, ll, lr = dfs(root.left)\n",
    "                ret[1] = lr + 1\n",
    "                ret[0] = max(ret[0], lm)\n",
    "            if root.right:\n",
    "                rm, rl, rr = dfs(root.right)\n",
    "                ret[2] = rl + 1\n",
    "                ret[0] = max(ret[0], rm)\n",
    "            ret[0] = max(ret)\n",
    "            return ret\n",
    "        return dfs(root)[0]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = 0\n",
    "\n",
    "    def dfs(self, root, father, lp, rp):\n",
    "        if root == None:\n",
    "            return\n",
    "        if father != None:\n",
    "            if father.left == root:\n",
    "                lp[root] = rp[father] + 1\n",
    "            else:\n",
    "                rp[root] = lp[father] + 1\n",
    "        self.res = max(self.res, lp[root], rp[root])\n",
    "        self.dfs(root.left, root, lp, rp)\n",
    "        self.dfs(root.right, root, lp, rp)\n",
    "\n",
    "    def longestZigZag(self, root: Optional[TreeNode]) -> int:\n",
    "        if root == None:\n",
    "            return 0\n",
    "        ## lp[root] 表示以 root 节点为重点, 且 root 是左子节点的最长交错路径\n",
    "        lp, rp = collections.defaultdict(int), collections.defaultdict(int)\n",
    "        self.dfs(root.left, root, lp, rp)\n",
    "        self.dfs(root.right, root, lp, rp)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestZigZag(self, root: Optional[TreeNode]) -> int:\n",
    "        zig, zag, neverMax = self.helpLongestZigZag(root)\n",
    "        return max(zig, zag, neverMax)\n",
    "    \n",
    "    def helpLongestZigZag(self, root: Optional[TreeNode]) -> int:\n",
    "        leftZig, leftZag, rightZig, rightZag = -1, -1, -1, -1\n",
    "        nmLeft, nmRight = -1, -1\n",
    "        neverMax = -1\n",
    "        if root.left:\n",
    "            leftZig, leftZag, nmLeft = self.helpLongestZigZag(root.left)\n",
    "            selfZig = leftZag+1\n",
    "        else:\n",
    "            leftZig, leftZag = 0, 0\n",
    "            selfZig = 0\n",
    "        if root.right:\n",
    "            rightZig, rightZag, nmRight = self.helpLongestZigZag(root.right)\n",
    "            selfZag = rightZig +1\n",
    "        else:\n",
    "            rightZig, rightZag = 0, 0\n",
    "            selfZag = 0\n",
    "        \n",
    "        neverMax = max(selfZig, selfZag, leftZig, leftZag, rightZig, rightZag, nmLeft, nmRight)\n",
    "        return selfZig, selfZag, neverMax\n",
    "\n",
    "        \n",
    "        \n",
    "        \n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
